package SwordFingerOffer;

public class Q55_2_BalanceTree {
    //判断平衡二叉树
    static class Info {
        boolean isBalance; //平衡否
        int depth; //深度

        public Info(boolean isBalance, int depth) {
            this.isBalance = isBalance;
            this.depth = depth;
        }
    }
    public static boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        return process(root).isBalance;
    }

    public static Info process(TreeNode root) {
        if (root == null){
            return new Info(true, 0);
        }

        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        //条件

        int depth = Math.max(leftInfo.depth, rightInfo.depth) + 1;
        boolean isBalance = leftInfo.isBalance && rightInfo.isBalance
                && Math.abs(leftInfo.depth - rightInfo.depth) <= 1;

        return new Info(isBalance, depth);
    }
}
